package com.kabuda.hot100.子串.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author kabuda
 * @create 2025-02-04 9:46
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * <p>
 * 子数组是数组中元素的连续非空序列。
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 */
public class t560_和为K的子数组 {

    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{1, 2, 1, 4, 2, 2}, 4));
    }


    /**
     * @param nums
     * @param k
     * @return 我们可以基于方法一利用数据结构进行进一步的优化，我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j 来判断是否符合条件，这一步是否可以优化呢？答案是可以的。
     *
     *
     * 我们定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：
     * pre[i]=pre[i−1]+nums[i]
     * 那么 [j..i] 这个子数组和为 k 」这个条件我们可以转化为
     * pre[i]−pre[j−1]==k
     * 简单移项可得符合条件的下标 j 需要满足
     * pre[j−1]==pre[i]−k
     */
    public static int subarraySum(int[] nums, int k) {
        // key：前缀和，value：对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    /**
     * 暴力破解法
     *
     * @param nums
     * @param k
     * @return
     */
    public static int violenceSubarraySum(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int begin = nums[i];
            int need = k - begin;
            if (need == 0) {
                result++;
            }
            for (int j = i + 1; j < nums.length; j++) {
                need -= nums[j];
                if (need == 0) {
                    result++;
                }
            }
        }
        return result;
    }
}
